package algorithm.linkedlist;

import algorithm.model.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * leetcode : https://leetcode.com/problems/intersection-of-two-linked-lists/description/
 * Difficulty : Easy
 *
 * 给两个链表，找到两个链表的相交的节点，返回该节点
 *
 * Notes:
 * 如果链表没有相交，则返回null
 * 链表必须保持其原有的数据结构
 * 两个链表没有环【这个条件很重要】
 * 最优解的时间复杂度为 O(n), 空间复杂度为O(1)
 *
 * 两个思路，
 * 1）HashSet，遍历的同时添加节点，如果添加失败则说明这是交点。空间复杂度O(N)
 * 2）两个遍历一遍找到长度，然后把长的先向后移动长度的差值个节点，然后一起向后移动，相等则是交点。空间复杂度O(1)
 * @Author Antony
 * @Since 2018/7/16 14:30
 */
public class IntersectionOfTwoLinkedLists {

    /**
     * beats 100.0% - 1ms
     * leetcode上看到的方法，很精妙
     * https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49785/Java-solution-without-knowing-the-difference-in-len!
     *
     * 思路：
     * ListA 和 ListB逐个向后迭代两个节点，a 和 b
     * a到头了就把指针指向headB，b到头了就把指针指向headA。
     * PS：这一步很关键！通过这一步，去掉了两个链表长度的不统一，也就是说，遍历到两个链表的交点的距离变成相等的长度了
     *
     * 假设headA的长度为 m 相较于x1, headB的长度为 n 相较于x2.
     * 那么可以有等式 m-x1 = n-x2
     * 交换项得到 m+x2 = n+x1. 这就表示：遍历一遍m再遍历到x2 = 遍历一遍n再遍历到x1
     * 也就是两个链表拼接之后迭代一遍遇到的节点。
     *
     * 其实很简单：
     * 如果有交点，假设相交前的长度分别为 A1, B1
     * 相交后到结尾的长度为C
     * 那么：
     * headA遍历一遍到相交，走过的长度为 A1+C+B1
     * headB遍历一遍到相交，走过的长度为 B1+C+A1
     * 可以看到，走过的距离是一样的，并且必然在相交点相遇。
     *
     * 这样如果两个链表有交点
     * 那么 a==b 的点就是交点
     * 否则 a==b 的点是null，也就是两个链表的尾节点
     * 所以只要遇到 a==b 的时候就停止迭代, 返回节点即可
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB){
        // boundary check
        if(headA == null || headB == null) return null;

        ListNode a = headA;
        ListNode b = headB;

        while(a != b){
            a = a==null? headB : a.next;
            b = b==null? headA : b.next;
        }

        return a;
    }



    /**
     * beats 100.0% - 1ms
     * 时间复杂度 O(N), 空间复杂度O(1)
     *
     * 思路：
     * 两个链表各自遍历一遍，找到长度LA和LB
     * 把长的链表先向后移动 |LA-LB| 个长度，然后两个链表再一起向后移动
     * 节点相等的就是相交点
     */
    public ListNode getIntersectionNode_useLength(ListNode headA, ListNode headB) {
        int lengthA = 0;
        int lengthB = 0;
        ListNode LA = headA;
        ListNode LB =  headB;

        // 找到两个链表长度
        while(headA != null){
            lengthA++;
            headA = headA.next;
        }
        while(headB != null){
            lengthB++;
            headB = headB.next;
        }

        // 计算长度差值，并且把长的向后移动差值的长度
        int differ = lengthA - lengthB;
        if(differ > 0){
            while(differ != 0){
                LA = LA.next;
                differ--;
            }
        }else{
            while(differ != 0){
                LB = LB.next;
                differ++;
            }
        }

        while(LA != null && LB != null){
            if(LA == LB){
                return LA;
            }
            LA = LA.next;
            LB = LB.next;
        }

        return null;
    }

    /**
     * 时间复杂度O(N), 空间复杂度O(N)
     * beats 10.88% - 12ms
     *
     * 思路：使用HashSet，挨个遍历A和B，添加失败的就是交点
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode_useSet(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        while(headA != null){
            set.add(headA);
            headA = headA.next;
        }
        while(headB != null){
            if(!set.add(headB)){
                return headB;
            }
            headB = headB.next;
        }

        return null;
    }
}
